#include "graph.h"

bool initQueue(queue & q){
    q.head = 0;
    q.tail = 0;
    for (int i = 0; i < MAX_VEX_NUM+1; i++){
        q.elems[i] = -1;
    }
    return true;
}

bool inQueue(queue & q, int elem){
    int t = (q.tail + 1) % (MAX_VEX_NUM + 1);
    if(t!=q.head){
        q.elems[q.tail] = elem;
        q.tail += 1;
        q.tail %= (MAX_VEX_NUM + 1);
        return true;
    }
    else{
        std::cout << "队满溢出！" << std::endl;
        return false;
    }
}

bool deQueue(queue & q, int & elem){
    if(q.head == q.tail){
        std::cout << "队空 !" << std::endl;
        return false;
    }
    elem = q.elems[q.head];
    q.head ++;
    q.head %= (MAX_VEX_NUM+1);
    return true;
}

bool initStack(stack & s){
    s.top = 0;
    s.bottom = 0;
    s.len = 0;
    for(int i = 0; i < MAX_VEX_NUM; ++i){
        s.elems[i] = -1;
    }
    return true;
}

bool popStack(stack & s, int & elem){
    if(s.top == s.bottom){
        std::cout << "栈空!"<< std::endl;
        return false;
    }
    s.top--;
    elem = s.elems[s.top];

    return true;
}

bool pushStack(stack & s, int elem){
    if(s.top == MAX_VEX_NUM-1){
        std::cout << "栈满 ！"<< std::endl;
        return false;
    }
    s.elems[s.top] = elem;
    s.top++;
    s.len = s.top;
    return true;
}

bool createMGraph(matGraph &graph){
    // 无向图创建
    int kind = -1;
    std::cout << "请输入图类型： ";
    std::cin >> kind;
    switch(kind){
        // case 0:
        //     graph.kind = graphKind::DG;
        //     break;
        // case 1:
        //     graph.kind = graphKind::DN;
        //     break;
        case 2:
            graph.kind = UDG;
            break;
        case 3:
            graph.kind = UDN;
            break;
        default:
            std::cout << "graph kind enter error !" << std::endl;
            return false;
    }
    std::cout << "节点个数： ";
    std::cin >> graph.vex_num;

    std::cout << "边的条数： ";
    std::cin >> graph.arc_num;

    std::cout << "输入所有节点值：" << std::endl;
    for (int i = 0; i < graph.vex_num; i++){
        std::cin >> graph.vexs[i];
    }
    for(int i = 0; i < graph.vex_num; i++){
        for (int j = 0; j < graph.vex_num; j++){
            graph.arcs[i][j] = {INFINITY, NULL};
        }
    }

    int vex1, vex2;
    int weight = 1;
    std::cout << "请输入各边(N N W):" << std::endl;
    for(int i = 0; i < graph.arc_num; i++){
        weight = 1;
        std::cin >> vex1 >> vex2;
        if(graph.kind == UDN) std::cin >> weight;
        graph.arcs[vex1-1][vex2-1] = {weight, NULL};
        graph.arcs[vex2-1][vex1-1] = {weight, NULL};
    }

    return true;
}

bool createALGraph(alGraph &graph){
    // 无向图创建
    int kind = -1;
    std::cout << "请输入图类型： ";
    std::cin >> kind;
    switch(kind){
        // case 0:
        //     graph.kind = graphKind::DG;
        //     break;
        // case 1:
        //     graph.kind = graphKind::DN;
        //     break;
        case 2:
            graph.kind = UDG;
            break;
        case 3:
            graph.kind = UDN;
            break;
        default:
            std::cout << "graph kind enter error !" << std::endl;
            return false;
    }
    std::cout << "节点个数： ";
    std::cin >> graph.vex_num;

    std::cout << "边的条数： ";
    std::cin >> graph.arc_num;

    std::cout << "输入所有节点值：" << std::endl;
    for (int i = 0; i < graph.vex_num; i++){
        std::cin >> graph.vexs[i].vex_value;
        graph.vexs[i].first_arc = NULL;
    }

    int vex1, vex2;
    int weight = 1;
    arcNode * p;
    std::cout << "请输入各边(N N W):" << std::endl;
    for (int i = 0; i < graph.arc_num; i++)
    {
        weight = 1;
        std::cin >> vex1 >> vex2;
        if(graph.kind == UDN) std::cin >> weight;
        p = (arcNode*)malloc(sizeof(arcNode));
        p->weight = weight;
        p->target_vex = vex2 - 1;
        p->next_arc = graph.vexs[vex1-1].first_arc;
        graph.vexs[vex1-1].first_arc = p;

        p = (arcNode*)malloc(sizeof(arcNode));
        p->weight = weight;
        p->target_vex = vex1 - 1;
        p->next_arc = graph.vexs[vex2 - 1].first_arc;
        graph.vexs[vex2 - 1].first_arc = p;
    }

    return true;
}

arcNode * getFisrtAdj(alGraph & graph, int vex){
    return graph.vexs[vex].first_arc;
}
// 
arcNode * getNextAdj(alGraph & graph, arcNode * current_adj){
    return current_adj->next_arc;
}

// dfs
bool visited[MAX_VEX_NUM];
bool (*visitFunc)(vexNode & vex);
bool dfsNodes(alGraph & graph, int vex){
    visited[vex] = true;
    visitFunc(graph.vexs[vex]);
    for(arcNode * p = getFisrtAdj(graph, vex); p != NULL; p = p->next_arc){
        if(!visited[p->target_vex]){
            dfsNodes(graph, p->target_vex);
        }
    }
    return true;
}

bool dfsNodes(matGraph& graph, int vex){
    visited[vex] = true;
    for(int i = 0; i < graph.vex_num; i++){
        if(!visited[i] && graph.arcs[vex][i].adj < INFINITY){
            dfsNodes(graph, i);
        }
    }
    return true;
}

bool dfsTraverse(alGraph & graph, bool(* visit)(vexNode & vex)){
    for (int i = 0; i < graph.vex_num; i++){
        visited[i] = false;
    }
    visitFunc = visit;

    for(int i = 0; i < graph.vex_num; i++){
        if(!visited[i]){
            dfsNodes(graph, i);
        }
    }

    return true;
}

// bfs
bool bfsTraverse(alGraph & graph, bool (*visit)(vexNode & vex)){
    queue q;
    initQueue(q);
    for(int i=0; i<graph.vex_num; i++){
        visited[i] = false;
    }

    int elem;
    for(int i=0; i<graph.vex_num; i++){
        if(!visited[i]){
            visit(graph.vexs[i]);
            visited[i] = true;
            inQueue(q, i);
            while(q.head != q.tail){
                deQueue(q, elem);
                for(arcNode * p = graph.vexs[elem].first_arc; p != NULL; p = p->next_arc){
                    if(!visited[p->target_vex]){
                        visit(graph.vexs[p->target_vex]);
                        visited[p->target_vex] = true;
                        inQueue(q, p->target_vex);
                    }
                }
            }
        }
    }

    return true;
}

bool isConnected(matGraph & graph){
    for(int i = 0; i < graph.vex_num; i++){
        visited[i] = false;
    }
    visitFunc = [](vexNode & vex)->bool{};      // 仅仅判断连通性，不需要进行其他操作，使用一个无操作的匿名函数
    dfsNodes(graph, 0);
    for (int i = 0; i < graph.vex_num; i++){
        if (!visited[i]){
            return false;
        }
    }
    return true;
}

bool isConnected(alGraph & graph){
    for(int i = 0; i < graph.vex_num; i++){
        visited[i] = false;
    }
    visitFunc = [](vexNode & vex)->bool{};      // 仅仅判断连通性，不需要进行其他操作，使用一个无操作的匿名函数
    dfsNodes(graph, 0);
    for (int i = 0; i < graph.vex_num; i++){
        if (!visited[i]){
            return false;
        }
    }
    return true;
}

bool miniSpanTreePrime(matGraph & graph, int start){
    if(!isConnected(graph)){
        std::cout << "输入的图不是一个连通图. " << std::endl;
        return false;
    }
    closeEdge edges;
    start -= 1;
    edges[start].low_cost = 0;
    edges[start].adj_vex = start;
    for (int i = 0; i < MAX_VEX_NUM; i++) {
        if(i != start)
            edges[i] = {start, graph.arcs[start][i].adj};
    }

    for(int i = 0; i < graph.vex_num; ++i) {
        start = miniEdge(edges, graph);
        if(start < 0) {
            return true;
        }
        std::cout << "node "<< edges[start].adj_vex << " value: " << graph.vexs[edges[start].adj_vex]
                << "-----node " << start << " value:" << graph.vexs[start] << std::endl;

        edges[start].low_cost = 0;

        for( int i = 0; i < graph.vex_num; i++){
            if(graph.arcs[start][i].adj < edges[i].low_cost){
                edges[i].low_cost = graph.arcs[start][i].adj;
                edges[i].adj_vex = start;
            }
        }
    }
    return true;
}

int miniEdge(closeEdge & edges, matGraph & graph){
    int min = INFINITY;
    int index = -1;
    for (int i = 0; i < graph.vex_num; ++i){
        if(edges[i].low_cost> 0 && edges[i].low_cost < min){
            min = edges[i].low_cost;
            index = i;
        }
    }
    // 返回和已经并入生成树中节点最近的节点的位置
    return index;
}

bool sortEdges(matGraph & graph, Edges & edge){
    if(graph.arc_num >= MAX_VEX_NUM){
        std::cout << "边数过多 ！" << std::endl;
        return false;
    }
    int index = 0;
    for(int i = 0; i < graph.vex_num; i++){
        for(int j = i+1; j < graph.vex_num; j++){
            if (graph.arcs[i][j].adj < INFINITY){
                edge[index] = {i, j, graph.arcs[i][j].adj};
                index++;
            }
        }
    }

    Edge tmp;
    for(int i = 0; i < graph.arc_num; i++){
        for(int j = 0; j < graph.arc_num-i-1; j++){
            if(edge[j].weight > edge[j+1].weight){
                tmp = edge[j];
                edge[j] = edge[j+1];
                edge[j] = tmp;
            }
        }
    }
    return true;
}

bool miniSpanTreeKruskal(matGraph & graph){
    Edges edges;
    Edges mini_tree;
    assist vex_aux;
    sortEdges(graph, edges);
    for(int i = 0; i < graph.vex_num; ++i){
        vex_aux[i] = {i, -1};
    }

    int arc_used = 0;
    int sign = 0;
    for(int i = 0; i < graph.arc_num; ++i){
        if(vex_aux[edges[i].init_vex].sign != edges[i].dest_vex\
         || (-1==vex_aux[edges[i].init_vex].sign && vex_aux[edges[i].dest_vex].sign== -1)){
             mini_tree[arc_used] = edges[i];
             arc_used ++;
        }
        if(graph.vex_num -1 == arc_used) break;
    }

    // output the tree
    for(int i = 0; i < arc_used; i ++){
        std::cout << "node " << mini_tree[i].init_vex;
        std::cout << " ----- node" << mini_tree[i].dest_vex;
        std:: cout << "     edge weight " << mini_tree[i].weight << std::endl;
    }

    return true;
}

bool shortPathDijkstra(matGraph & graph, pathMatrix & path, sPathTable & d_table, const int init_vex){
    bool in_path[MAX_VEX_NUM];
    for(int i = 0; i < graph.vex_num; i ++){
        in_path[i] = false;
        d_table[i] = {i, graph.arcs[init_vex][i].adj};
        initStack(path[i]);
        // for(int j = 0; j < graph.vex_num; j++){
        //     path[i][j] = false;
        // }
        if(d_table[i].weight < INFINITY){
            pushStack(path[i], init_vex);
            pushStack(path[i], i);
        }
    }
    d_table[init_vex].weight = 0;
    in_path[init_vex] = true;
    pushStack(path[init_vex], init_vex);
    int min = INFINITY;
    int vex_t = init_vex;
    for(int i = 0; i < graph.vex_num; i++){
        min = INFINITY;
        for(int j = 0; j < graph.vex_num; j++){
            if(!in_path[j] && d_table[j].weight < min){
                vex_t = j;
                min = d_table[j].weight;
            }
        }
        in_path[vex_t] = true;
        int j_min = -1;
        for(int j = 0; j < graph.vex_num; j++){
            if(!in_path[j] && (min + graph.arcs[vex_t][j].adj) < d_table[j].weight){
                d_table[j].weight = min + graph.arcs[vex_t][j].adj;
                // path[j][j] = true;
                j_min = j;
            }
        }
        if(-1 != j_min){
            path[j_min] = path[vex_t];
            pushStack(path[j_min], j_min);
        }
    }
    return true;
}

bool putPathDijkstra(matGraph & graph, pathMatrix & path){
    for(int i = 0; i < graph.vex_num; i++){
        for(int j = 0; j < path[i].len-1; j++){
            int k = path[i].elems[j];
            std::cout << "node " << k
                    << "  node value " << graph.vexs[k]
                    << " -----> node " << path[i].elems[j+1]
                    << "  \t\tarc weight : " << graph.arcs[k][path[i].elems[j+1]].adj << std::endl;
        }
        std::cout << "node " << path[i].elems[path[i].len-1]
                    << "  node value " << graph.vexs[path[i].elems[path[i].len-1]] << std::endl;;
        std::cout << std::endl;
    }
}

bool shortPathFloyd(matGraph & graph, fPath & path, dMatrix & dist){
    for(int i = 0; i < graph.vex_num; i++){
        for(int j = 0; j < graph.vex_num; j++){
            dist[i][j] = graph.arcs[i][j].adj;
            for(int k = 0; k < graph.vex_num; k++)
                path[i][j][k] = false;
            
            if(dist[i][j] < INFINITY){
                path[i][j][i] = true;
                path[i][j][j] = true;
            }
        }
        // matGraph 中节点到自身距离设置为INFINITY, 此处会产生错误
        dist[i][i] = 0;
    }

    for(int i = 0; i < graph.vex_num; i++){
        for(int j = 0; j < graph.vex_num; j++){
            for(int k = 0; k < graph.vex_num; k++){
                if(dist[j][i] + dist[i][k] < dist[j][k]){
                    dist[j][k] = dist[j][i] + dist[i][k];
                   dist[k][j] = dist[j][i] + dist[i][k];
                    for(int m = 0; m < graph.vex_num; m++){
                        path[j][k][m] = path[j][i][m] || path[i][k][m];
                    }
                }
                // if(dist[i][k] + dist[j][k] < dist[i][j]){
                //     dist[i][j] = dist[i][k] + dist[j][k];
                //     for(int m = 0; m < graph.vex_num; m++){
                //         path[i][j][m] = path[i][k][m] || path[k][j][m];
                //     }
                // }
            }
        }
    }

    return true;
}

stack shortest_path;
bool getPathFloyd(fPath &path, int start, int end, int vex_num){
    if(!visited[end]){
        pushStack(shortest_path, end);
        visited[end] = true;
    }
    int i = 0;
    for(i=0; i<vex_num; i++){
        if(path[start][end][i] && !visited[i] && i != start)
            break;
    }
    if(vex_num == i){
        if(!visited[i])
            pushStack(shortest_path, start);
        visited[i] = true;
        return true;
    }
    if(getPathFloyd(path, i, end, vex_num)){
        if(getPathFloyd(path, start, i, vex_num)){
            return true;
        }else{
            return false;
        }
    }else{
        return false;
    }
}

// 输出路径
bool putPathFloyd(matGraph & graph, fPath & path, int start, int end){
    for(int i = 0; i < graph.vex_num; i++){
        visited[i] = false;
    }
    initStack(shortest_path);
    int elem = -1;
    std::cout << "node " << start << " value " << graph.vexs[start] << std::endl;
    if(getPathFloyd(path, start, end, graph.vex_num)){
        while(shortest_path.top != shortest_path.bottom){
            popStack(shortest_path, elem);
            std::cout << "node " << elem << " value " << graph.vexs[elem] << std::endl;
        }
    }
    return true;
}
